package com.gxc.integer;

import java.util.Arrays;

/**
 * 3007. 价值和小于等于 K 的最大数字

 * 给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x，2x，3x 等位置处
 * 设置位
 *  的数目（从最低有效位开始）。下面的表格包含了如何计算价值的例子。
 *
 * x	num	Binary Representation	Price
 * 1	13	000001101	3
 * 2	13	000001101	1
 * 2	233	011101001	3
 * 3	13	000001101	1
 * 3	362	101101010	2
 *
 *
 * num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价 的。
 *
 * 请你返回 最大 的廉价数字。
 */
public class FindMaximumNumber {

    public static void main(String[] args) {
        System.out.println(1>>1);
        System.out.println(Long.numberOfLeadingZeros(1));
        System.out.println(Long.numberOfLeadingZeros(2));
        System.out.println(Long.numberOfLeadingZeros(17));

        System.out.println(handle(9, 1));
        System.out.println(handle(7, 2));
        System.out.println(findMaximumNumber(7, 2));
    }

    public static long handle(long k, int x) {
        int sum = 0;
        int i = 1;
        while (sum<=k) {
            int j = i>>(x-1);
            if ((j & 1) ==1) sum++;
            while (j!=0) {
                j = j>>x;
                if ((j & 1) ==1) sum++;
            }
            i++;
        }
        return i-2;
    }

    public static long handle2(long k, int x) {
        int i = (int) Math.pow(2, x-1);
        int base = i;
        int sum = 1;
        while (sum<=k) {

        }
        return 0;
    }

    public static long findMaximumNumber(long k, int x) {
        long l = 1, r = (k + 1) << x;
        while (l < r) {
            long m = (l + r + 1) / 2;
            if (accumulatedPrice(x, m) > k) {
                r = m - 1;
            } else {
                l = m;
            }
        }
        return l;
    }

    public static long accumulatedPrice(int x, long num) {
        long res = 0;
        int length = 64 - Long.numberOfLeadingZeros(num);
        for (int i = x; i <= length; i += x) {
            res += accumulatedBitPrice(i, num);
        }
        return res;
    }

    public static long accumulatedBitPrice(int x, long num) {
        long period = 1L << x;
        //  period / 2  period 的次低位有一半的个数 1
        //  num / period  num >>2 num会出现多少次 period
        //  period / 2 * (num / period) 次低位是1 的总个数
        long res = period / 2 * (num / period);
        //如果 num % period > period / 2  计算剩余周期的x位有多少个1
        if (num % period >= period / 2) {
            res += num % period - (period / 2 - 1);
        }
        return res;
    }


    class Solution {
        public long findMaximumNumber(long k, int x) {
            this.x = x;
            // 开区间二分，原理见 https://www.bilibili.com/video/BV1AP41137w7/
            long left = 0;
            long right = (k + 1) << x;
            while (left + 1 < right) {
                long mid = (left + right) >>> 1;
                if (countDigitOne(mid) <= k) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            return left;
        }

        private int x;
        private long num;
        private long memo[][];

        private long countDigitOne(long num) {
            this.num = num;
            int m = 64 - Long.numberOfLeadingZeros(num);
            memo = new long[m][m + 1];
            for (long[] row : memo) {
                Arrays.fill(row, -1);
            }
            return dfs(m - 1, 0, true);
        }

        private long dfs(int i, int cnt1, boolean isLimit) {
            if (i < 0) {
                return cnt1;
            }
            if (!isLimit && memo[i][cnt1] != -1) {
                return memo[i][cnt1];
            }
            int up = isLimit ? (int) (num >> i & 1) : 1;
            long res = 0;
            for (int d = 0; d <= up; d++) { // 枚举要填入的数字 d
                res += dfs(i - 1, cnt1 + (d == 1 && (i + 1) % x == 0 ? 1 : 0), isLimit && d == up);
            }
            if (!isLimit) {
                memo[i][cnt1] = res;
            }
            return res;
        }
    }

    class Solution2 {
        public long findMaximumNumber(long k, int x) {
            long l = 1, r = (k + 1) << x;
            while (l < r) {
                long m = (l + r + 1) / 2;
                if (accumulatedPrice(x, m) > k) {
                    r = m - 1;
                } else {
                    l = m;
                }
            }
            return l;
        }

        public long accumulatedPrice(int x, long num) {
            long res = 0;
            int length = 64 - Long.numberOfLeadingZeros(num);
            for (int i = x; i <= length; i += x) {
                res += accumulatedBitPrice(i, num);
            }
            return res;
        }

        public long accumulatedBitPrice(int x, long num) {
            long period = 1L << x;
            long res = period / 2 * (num / period);
            if (num % period >= period / 2) {
                res += num % period - (period / 2 - 1);
            }
            return res;
        }
    }

    class Solution3 {
        public long findMaximumNumber(long k, int x) {
            long num = 0;
            long pre1 = 0;
            for (long i = 63 - Long.numberOfLeadingZeros((k + 1) << x); i >= 0; i--) {
                long cnt = (pre1 << i) + (i / x << i >> 1);
                if (cnt > k) {
                    continue;
                }
                k -= cnt;
                num |= 1L << i;
                if ((i + 1) % x == 0) {
                    pre1++;
                }
            }
            return num - 1;
        }
    }


}